package com.wyy.test.skiplist;

import java.util.Random;

/**
 * @Date: 2023/3/13
 * @Author: wyy
 */
public class SkipList<Data extends Comparable<Data>> {
    private int maxLevel;

    private Node<Data> head;

    private Random random;

    static class Node<Data extends Comparable<Data>> {
        private Data data;

        /**
         * 第几层的next节点
         */
        private Node<Data> forwards[];

        private int level;

        public Node(Data data, int level) {
            this.data = data;
            this.level = level;
        }
    }

    public SkipList(int maxLevel) {
        this.maxLevel = maxLevel;
        this.head = new Node<>(null, maxLevel);
        this.random = new Random();
    }

    private int randomLevel() {
        int level = 0;
        while (level < maxLevel && random.nextInt() < 0.5) {
            level++;
        }
        return level;
    }

    public void insert(Data data) {
        int level = randomLevel();
        Node<Data> newNode = new Node<>(data, level);

        /**
         * 这些节点需要更新对应level的forward
         */
        Node<Data> update[] = new Node[level];

        for (int i = 0; i < level; i++) {
            update[i] = head;
        }

        for (int level_ = level - 1; level_ > 0; level_--) {
            Node<Data> temp = head;
            while (temp.forwards[level_] != null &&
                    temp.forwards[level_].data != null
                    && temp.forwards[level_].data.compareTo(data) < 0) {
                temp = temp.forwards[level_];
            }
            update[level_] = temp;
        }

        for (int i = 0; i < level; i++) {
            newNode.forwards[i] = update[i].forwards[i];
            update[i].forwards[i] = newNode;
        }
    }
}
